package Leetcode.网格图;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/4/28 14:38
 * @Description:
 *
 * 边界着色
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
 *
 * 如果两个方块在任意 4 个方向上相邻，则称它们 相邻 。
 *
 * 如果两个方块具有相同的颜色且相邻，它们则属于同一个 连通分量 。
 *
 * 连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：
 *
 * 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
 * 在网格的边界上（第一行/列或最后一行/列）
 * 请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色。
 *
 * 并返回最终的网格 grid 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
 * 输出：[[3,3],[3,2]]
 * 示例 2：
 *
 * 输入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
 * 输出：[[1,3,3],[2,3,3]]
 * 示例 3：
 *
 * 输入：grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
 * 输出：[[2,2,2],[2,1,2],[2,2,2]]
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 50
 * 1 <= grid[i][j], color <= 1000
 * 0 <= row < m
 * 0 <= col < n
 */

public class colorBorder {
    public static void main(String[] args) {
        int[][] arr = {{1,2,2},{2,3,2}};
        int row = 0, col = 1, color = 3;
        /*
        1   2   3
        2   3   2

        1   3   3
        2   3   3
         */
        int[][] ints = new colorBorder().colorBorder(arr, row, col, color);
        for (int[] a : ints) {
            System.out.println(Arrays.toString(a));
        }
        System.out.println();
    }

    /**
     *  如果两个方块在任意 4 个方向上相邻，则称它们 相邻 。
     *
     * 如果两个方块具有相同的颜色且相邻，它们则属于同一个 连通分量 。
     *
     * 连通分量的边界 是指连通分量中满足下述条件之一的所有网格块：
     *
     * 在上、下、左、右任意一个方向上与不属于同一连通分量的网格块相邻
     * 在网格的边界上（第一行/列或最后一行/列）
     * @param grid
     * @param row
     * @param col
     * @param color
     * @return
     */
    boolean[][] visited;
    int m , n;
    int target;
    int color;
    int[][] grid;

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {

        m = grid.length;
        n = grid[0].length;
        visited = new boolean[m][n];
        target = grid[row][col];
        this.color = color;
        this.grid = grid;

        dfs(row,col,row,col);

        return grid;

    }

    private void dfs(int row, int col, int i, int i1) {
        if (row < 0
        || row >= m
        || col < 0
        || col >= n) {
            grid[i][i1] = color;
            return;
        }

        if (!visited[row][col]) {
            if (grid[row][col] == target) {
                visited[row][col] = true;
                dfs(row + 1, col, row, col);
                dfs(row, col + 1, row, col);
                dfs(row - 1, col, row, col);
                dfs(row, col - 1, row, col);
            } else {
                grid[i][i1] = color;
            }
        }

    }


}
